package tree.balanceSearchTree;

import pojo.TreeNode;

/**
 * 功能描述: 平衡搜索二叉树
 *  1. 是一个平衡树
 *      左子树的高度，和右子树的高度，差值不大于1
 *      可以是左子树高, 也可以是右子树 高, 反正高度差不可以超过1
 *  2. 是一个搜索二叉树
 *      左子树的所有节点的值，小于等于根节点的值
 *      右子树的所有节点的值，大于等于根节点的值
 * 2024/05/19
 * <p>
 * ZhangYi
 */
public class BalanceSearchTreeUtils {

    /***
     * 确认要返回的 info 信息
     */

    public static class Info{
        /***
         *  平衡树
         */
        private boolean isBalance;
        /***
         * 高度
         */
        private int height;
        /***
         * 是否是搜索二叉树
         */
        private boolean isBST;//
        /***
         * 最小值
         */
        private int min;
        /***
         * 最大值
         */
        private int max;

        public Info(boolean isBalance,
                    int height,
                    boolean isBST,
                    int min,
                    int max) {
            this.isBalance = isBalance;
            this.height = height;
            this.isBST = isBST;
            this.min = min;
            this.max = max;
        }
    }


    /**
     * 功能描述: 是平衡搜索二叉树
     *
     * @param root
     * @return boolean
     */
    public static boolean isBalanceSearchTree(TreeNode root){
        if (root == null){
            return true;
        }

        return isBalanceSearchTreeHelper(root).isBalance && isBalanceSearchTreeHelper(root).isBST;

    }

    private static Info isBalanceSearchTreeHelper(TreeNode root) {
        if (root == null){
            return null;
        }

        Info leftInfo = isBalanceSearchTreeHelper(root.left);
        Info rightInfo = isBalanceSearchTreeHelper(root.right);


        int height = 0 ;
        int min = root.getId();
        int max = root.getId();
        if (leftInfo != null){
            max = Math.max(leftInfo.max,max);
            min = Math.min(leftInfo.min,min);
            height = Math.max(leftInfo.height,height);
        }
        if (rightInfo != null){
            max = Math.max(rightInfo.max,max);
            min = Math.min(rightInfo.min,min);
            height = Math.max(rightInfo.height,height);
        }

        height+=1;
        boolean isBalance = (leftInfo == null ? true : leftInfo.isBalance)
                && (rightInfo == null ? true: rightInfo.isBalance)
                && (leftInfo == null || rightInfo == null || Math.abs(leftInfo.height - rightInfo.height)<2);

        boolean isBST = (leftInfo == null ? true : leftInfo.isBST && leftInfo.max < root.getId())
                && (rightInfo == null ? true : rightInfo.isBST && root.getId()< rightInfo.min);
        return new Info(isBalance,height,isBST,min,max);
    }


    public static void main(String[] args) {
        TreeNode root = generateBalanceSearchTree();
        TreeNode root2 = generateNonBalanceSearchTree();

        System.out.println(isBalanceSearchTree(root));
        System.out.println(isBalanceSearchTree(root2));
    }



    private static TreeNode generateBalanceSearchTree() {
        TreeNode treeNode = new TreeNode(23,
                                         "1");
        treeNode.left = new TreeNode(12,
                                     "2");
        treeNode.left.left = new TreeNode(11,
                                          "4");


        treeNode.right = new TreeNode(34,
                                      "3");
        treeNode.right.left = new TreeNode(33,
                                           "6");
        treeNode.right.right = new TreeNode(35,
                                           "7");
        treeNode.right.right.right = new TreeNode(36,
                                                  "8");
        return treeNode;
    }

    private static TreeNode generateNonBalanceSearchTree() {
        TreeNode treeNode = new TreeNode(23,
                                         "1");
        treeNode.left = new TreeNode(12,
                                     "2");
        treeNode.left.left = new TreeNode(11,
                                          "4");
        treeNode.left.right = new TreeNode(13,
                                           "5");

        treeNode.left.left.left = new TreeNode(10,
                                               "9");
        treeNode.left.left.left.left = new TreeNode(9,
                                                    "10");
        treeNode.left.left.left.left.left = new TreeNode(8,
                                                         "11");

        treeNode.right = new TreeNode(34,
                                      "3");
        treeNode.right.left = new TreeNode(33,
                                           "6");
        treeNode.right.right = new TreeNode(35,
                                            "7");
        treeNode.right.right.right = new TreeNode(36,
                                                  "8");
        return treeNode;
    }
}
